public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null && cur.val != key) {
            parent = cur;
            if (cur.val > key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        if (cur == null) {
            return root;
        }
        if (cur.left == null || cur.right == null) {
            cur = cur.left == null ? cur.right : cur.left;
            if (parent != null) {
                if (parent.val > key) {
                    parent.left = cur;
                } else {
                    parent.right = cur;
                }
                return root;
            } else {
                return cur;
            }
        }

        TreeNode leftRightMost = cur.left;
        TreeNode leftRightMostParent = cur;
        while (leftRightMost.right != null) {
            leftRightMostParent = leftRightMost;
            leftRightMost = leftRightMost.right;
        }
        if (leftRightMostParent == cur){
            leftRightMostParent.left = leftRightMost.left;
        } else {
            leftRightMostParent.right = leftRightMost.left;
        }
        leftRightMost.left = cur.left;
        leftRightMost.right = cur.right;
        if (parent != null) {
            if (parent.val > key) {
                parent.left = leftRightMost;
            } else {
                parent.right = leftRightMost;
            }
            return root;
        } else {
            return leftRightMost;
        }
    }
}